# `random` module is used to shuffle field, see:
# https://docs.python.org/3/library/random.html#random.shuffle
import random
from typing import Final, Optional

# Empty tile, there's only one empty cell on a field:
EMPTY_MARK :Final[str] = 'x'

# Dictionary of possible moves if a form of:
# key -> delta to move the empty tile on a field.
MOVES : Final[dict[str,int]]= {
    'w': -4,
    's': 4,
    'a': -1,
    'd': 1,
}


def shuffle_field() -> list:
    field:list=list(range(1,16))+list(EMPTY_MARK)
    step:int=random.randint(10, 99)
    for _ in range(step):
      perform_move(field,random.choice(list(MOVES.keys())))
    if field==list(range(1,16))+list(EMPTY_MARK):
        shuffle_field()
    return field


def print_field(field:list) -> None:
    for item in range(4):
        print(field[item*4], field[item*4+1], field[item*4+2], field[item*4+3], sep='\t')


def is_game_finished(field:list) -> bool:
    """
    This function checks if the game is finished.

    :param field: current field state.
    :return: True if the game is finished, False otherwise.
    """
    wish_list:list = list(range(1,16))
    return field[:-1]==wish_list
    



def perform_move(field:list, key:str) -> Optional[list]:
    """
    Moves empty-tile inside the field.

    :param field: current field state.
    :param key: move direction.
    :return: new field state (after the move)
        or `None` if the move can't me done.
    """
    index_x:int=field.index(EMPTY_MARK)
    if key=='w'and index_x+MOVES['w'] >=0:
        field[index_x],field[index_x+MOVES['w']]=field[index_x+MOVES['w']],field[index_x]
        return field        
    elif key=='s'and index_x<12:
        field[index_x],field[index_x+MOVES['s']]=field[index_x+MOVES['s']],field[index_x]
        return field
    elif key=='a'and index_x%4!=0:
        field[index_x],field[index_x+MOVES['a']]=field[index_x+MOVES['a']],field[index_x]
        return field
    elif key=='d'and index_x%4!=3:
            field[index_x],field[index_x+MOVES['d']]=field[index_x+MOVES['d']],field[index_x]
            return field
    else: return None
    


def handle_user_input() -> Optional[str]:
    """
    Handles user input.

    List of accepted moves:
        'w' - up,
        's' - down,
        'a' - left,
        'd' - right

    :return: <str> current move.
    """
    print('Ваш ход:')
    user_input=input()
    if user_input in MOVES.keys():
        return user_input
    else: 
        print('Данная клавиша не поддерживается. Для движения используйте клавиши wasd')
        return None
        
    
    


def main() -> None:
    print('Добро пожаловать! Для перемещения пустого поля x пользуйтесь клавишами wasd')
    game_list:list=shuffle_field()
    print_field(game_list)
    count_turn:int=0 
    while (not is_game_finished(game_list)):
        move_key= None
        move_key=handle_user_input()
        if move_key is None:
          print_field(game_list)
          continue
        new_list:Optional[list]=perform_move(game_list,move_key)
        if new_list is not None:
            game_list=new_list
            count_turn+=1
            print_field(game_list)
        else: 
              print('Непозволительный ход - пустая клетка не может выходить за пределы поля')
              print_field(game_list)
    print('Вы восхитетельны! Вы смогли разгадать игру за ',count_turn, 'шагов')



if __name__ == '__main__':
    # See what this means:
    # http://stackoverflow.com/questions/419163/what-does-if-name-main-do
    main()
